//优美的排列
//测试链接：https://leetcode.cn/problems/beautiful-arrangement/
public class CountArrangement {
    int ans = 0;
    int[] num;
    public int countArrangement(int n) {
        num = new int[n+1];
        for(int i = 1; i <= n; i++) {
            num[i] = i;
        }
        dfs(1);
        return ans;
    }

    public void dfs(int pos) {
        if(pos == num.length) {
            ans++;
            return;
        }

        for(int i = pos; i < num.length; i++) {
            swap(pos,i);
            if(pos % num[pos] == 0 || num[pos] % pos == 0 ) {
                dfs(pos+1);
            }
            swap(pos,i);
        }
    }

    public void swap(int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
}
